import java.util.*;

public class num216 {
    public List<List<Integer>> combinationSum3(int k, int n) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> path = new ArrayList<>();
            int[] nums = new int[]{1,2,3,4,5,6,7,8,9};
            int temp = 0;
            dfs(k,n,res,path,nums,0,temp);
            return res;
        }

    private void dfs(int k, int n, List<List<Integer>> res, List<Integer> path, int[] nums, int depth, int temp) {
        if(depth > k) {
            return;
        }
        if(depth == k && temp == n) {
            res.add(new ArrayList<>(path));
            return;
        }
        for(int i = 0;i < 9; i ++) {
            if(!path.contains(nums[i])) {
                if(path.isEmpty()){
                path.add(nums[i]);
                temp += nums[i];
                dfs(k,n,res,path,nums,depth + 1,temp);
                path.remove(path.size() - 1);
                temp -= nums[i];
                }else {
                    if(path.get(path.size() - 1) > nums[i]) {
                        path.add(nums[i]);
                        temp += nums[i];
                        dfs(k,n,res,path,nums,depth + 1,temp);
                        path.remove(path.size() - 1);
                        temp -= nums[i];
                    }
                }
            }
        }
    }
}

